package LinkedList.反转链表_k组;

import LinkedList.ListNode;

public class Test {

    public ListNode reverseKGroup(ListNode head, int k) {

        if(head == null || k == 1) {
            return head;
        }

        // 创建一个虚拟节点（dummy）并将其next指针指向链表的头节点,处理边界条件,返回dummy的next为头节点
        ListNode dummy = new ListNode(-1);
        dummy.next = head;

        ListNode prev = dummy, cur = head, temp;

        // 遍历链表，统计链表的长度。
        int count = 0;
        while(head != null) {
            count++;
            head = head.next;
        }

        // 使用while循环处理链表。当链表剩余的节点数大于等于k时，进入循环。
        while(count >= k) {
            // 交换 k-1 次 就是反转k个
            for(int i = 1; i < k; i++) {
                temp = cur.next;
                cur.next = temp.next;
                temp.next = prev.next;
                prev.next = temp;
            }
            // 反转完一组进行下一组
            prev = cur;
            cur = cur.next;
            count -= k;
        }

        return dummy.next;
    }

}
